//2095 - 删除链表中的中间节点
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        prev.next = slow.next;
        return head;
    }
}
//328 - 奇偶链表
//方法一
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null ) // 头为空
            return null;
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;
        while(even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;//偶数的后一个永远在奇数后面
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
//方法二
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null ) // 头为空
            return null;
        if(head.next == null || head.next.next == null) //只有1个或2个，返回head
            return head;
        ListNode newHeadA = new ListNode();
        ListNode  A = newHeadA;
        ListNode newHeadB = new ListNode();
        ListNode B = newHeadB;
        ListNode cur = head;
        int count = 1;
        while(cur != null){
            if(count%2 != 0){//奇数位
                A.next = cur;
                A = cur;
            }else{//偶数位
                B.next = cur;
                B = cur;
            }
            cur = cur.next;
            count++;
        }
        A.next = newHeadB.next;//将奇数位的最后一个与偶数位的第一个连接起来
        B.next = null;//将最后一个置为空
        return newHeadA.next;
    }
}
public class Test {
}
